package sjp.demo.algorithm.doublepointer;

import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;

/**
 * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
 * <p>
 * 示例:
 * <p>
 * 输入: [0,1,0,3,12]
 * 输出: [1,3,12,0,0]
 * 说明:
 * <p>
 * 必须在原数组上操作，不能拷贝额外的数组。
 * 尽量减少操作次数。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/move-zeroes
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class MoveZeroes {
    public void moveZeroes(int[] nums) {
        /*
        思路：
        双指针都从0开始， 指针1寻找0， 指针2寻找非0，找到就交换， 然后指针1、指针2都+1
         */
        int a = 0;
        int b = 1;

        while (a < nums.length - 1 && b < nums.length) {
            if (nums[a] == 0) {
                // nums[a]为0 ，找不为0的nums[b]
                while (nums[b] == 0) {
                    b++;
                    if (b > nums.length - 1) {
                        return;
                    }
                }
                nums[a] = nums[b];
                nums[b] = 0;
            }
            a++;
            b++;

//            System.out.println(a + "," + b);
//            System.out.println(Arrays.toString(nums));
        }
    }

    /*
    想象成是两个数组，非0但按顺序放到第二个数组上，后面填0，现在把第二个数组去掉了直接用第一个数组来存
     */
    public void moveZeroes2(int[] nums) {
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[j++] = nums[i];
            }
        }
        while (j < nums.length) {
            nums[j++] = 0;
        }
    }

    @Test
    public void test() {
        int[] nums = new int[]{0, 1, 0, 3, 12, 0, 55};

        moveZeroes2(nums);
        Assert.assertArrayEquals("", new int[]{1, 3, 12, 55, 0, 0, 0}, nums);
    }
}
